package labuladong.动态规划;

public class 背包0_1问题 {
    /**
     * 0-1背包问题
     * @param W 背包所能容纳最大容量
     * @param N N件商品
     * @param weight 物品重量
     * @param value 物品价值
     * @return
     */
    public static int knapsack(int W, int N, int[] weight, int[] value) {
        int dp[][] = new int[N+1][W+1];
        for (int i=1; i<=N; i++) {
            for (int j=1; j<=W; j++) {
                if (j - weight[i-1] < 0) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-weight[i-1]] + value[i-1]);
                }
            }
        }
        return dp[N][W];
    }

    public static void main(String[] args) {
        System.out.println(knapsack(4, 3, new int[]{2, 1, 3}, new int[]{4, 2, 3}));
    }
}
